#include <bits/stdc++.h>

using namespace std;

class Solution
{
public:
    void traceback(vector<vector<int>> &res, vector<int> &road, int start, int n, int k)
    {
        if (road.size() == static_cast<size_t>(k))
        {
            res.push_back(road);
            return;
        }

        // for (int i = start; i <= n; i++)
        // {
        //     road.push_back(i);
        //     traceback(res, road, i + 1, n, k);
        //     road.pop_back();
        // }

        // pruning
        for (int i = start; i <= n - (k - static_cast<int>(road.size())) + 1; i++)
        {
            road.push_back(i);
            traceback(res, road, i + 1, n, k);
            road.pop_back();
        }
    }
    vector<vector<int>> combine(int n, int k)
    {
        vector<vector<int>> res;
        vector<int> road;
        if (n < k)
        {
            return res;
        }
        traceback(res, road, 1, n, k);
        return res;
    }
};

int main()
{
    Solution sol;
    vector<vector<int>> res = sol.combine(4, 2);
    for (auto vec : res)
    {
        for (auto num : vec)
        {
            cout << num << " ";
        }
        cout << endl;
    }
    return 0;
}